The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


Chapter 4
Twofish

Figure 4.1 shows an overview of the Twofish block cipher. Twofish uses a 16-round Feistel-like structure with additional whitening of the input and output. The only non-Feistel elements are the 1-bit rotates. The rotations can be moved into the F function to create a pure Feistel structure, but this requires an additional rotation of the words just before the output whitening step.

The plaintext is split into four 32-bit words. In the input whitening step, these are XORed with four key words. This is followed by 16 rounds. In each round, the two words on the left are used as input to the g functions. (One of them is rotated by 8 bits first.) The g function consists of four byte-wide key-dependent S-boxes, followed by a linear mixing step based on an MDS matrix. The results of the two g functions are combined using a Pseudo-Hadamard Transform (PHT), and two round key words are added. These two results are then XORed into the words on the right (one of which is rotated left by one bit first, the other is rotated right by one bit afterwards). The left and right halves are then swapped for the next round. After all the rounds, the swap of the last round is reversed, and the four words are XORed with four more key words to produce the ciphertext.

More formally, the 16 bytes of plaintext p0, ... , p15 are first split into four words P0, ..., P3 of 32 bits each using the little-endian convention.

In the input whitening step, these words are XORed with four words of the expanded key.

R0,i = PiKi i = 0,...,3

In each of the 16 rounds, the first two words are used as input to the function F, which also takes the round number as input. The third word is XORed with the first output of F and then rotated right by one bit. The fourth word is rotated left by one bit and then XORed with the second output word of F. Finally, the two halves are exchanged. Thus,

(Fr,0,Fr,1) = F(Rr,0,Rr,1,r)


Fig. 4.1.  Twofish
Rr+1,0 = ROR(Rr,2Fr,0,1)
Rr+1,1 = ROL(Rr,3,1) ⊕ Fr,1)
Rr+1,2 = Rr,0
Rr+1,3 = Rr,1

for r = 0, ..., 15 and where ROR and ROL are functions that rotate their first argument (a 32-bit word) left or right by the number of bits indicated by their second argument.

The output whitening step undoes the “swap” of the last round, and XORs the data words with four words of the expanded key.

Ci = R16,(i+2) mod 4Ki+4 i = 0,...,3

The four words of ciphertext are then written as 16 bytes c0, ..., c15 using the same little-endian conversion used for the plaintext.

4.1 The Function F

The function F is a key-dependent permutation on 64-bit values. It takes three arguments: two input words R0 and R1, and the round number r used to select the appropriate subkeys. R0 is passed through the g function, which yields T0. R1 is rotated left by eight bits and then passed through the g function to yield T1. The results T0 and T1 are then combined using a PHT and two words of the expanded key are added.

T0 = g(R0)
T1 = g(ROL(R1,8))
F0 = (T0 + T1 + K2r+8) mod 232
F1 = (T0 + 2T1 + K2r+9) mod 232

where (F0, F1) is the result of F. We also define the function F´ for use in our analysis. F´ is identical to the F function, except that it does not add any key blocks to the output. (The PHT is still performed.)

4.2 The Function g

The function g forms the heart of Twofish. The input word X is split into four bytes. Each byte is run through its own key-dependent S-box. Each S-box is an 8-bit permutation: it takes eight bits of input and produces eight bits of output. The four results are interpreted as components of a vector of length 4 over GF(28), and multiplied by the 4 × 4 MDS matrix (using the field GF(28) for the computations).

The resulting vector is interpreted as a 32-bit word which is the result of g.

where si are the key-dependent S-boxes and Z is the result of g. For this to be well-defined, we need to specify the correspondence between byte values and the field elements of GF(28). We represent GF(28) as GF(2)[x]/v(x), where v(x) = x8 + x6 + x5 + x3 + 1 is a primitive polynomial of degree 8 over GF(2). The field element a = å7i=0 aixi with ai ∈ GF(2) is identified with the byte value å7i=0 ai2i. This is in some sense the “natural” mapping; addition in GF(28) corresponds to a XOR of the bytes.

The MDS matrix is given by:

where the elements have been written as hexadecimal byte values using the above-defined correspondence.

4.3 The Key Schedule

The key schedule has to provide 40 words of expanded key K0, ..., K39, and the 4 key-dependent S-boxes used in the g function. Twofish is defined for keys of length N = 128, N = 192, and N = 256.

We define k = N/64. The key M consists of 8k bytes m0, ..., m8k-1. The bytes are first converted into 2k words of 32 bits each

and then into two word vectors of length k.

Me = (Mo,M2,...,M2k-2)
M0 = (M1,M3,...,M2k-1)

A third word vector of length k is also derived from the key. This is done by taking the key bytes in groups of eight, interpreting them as a vector over GF(28), and multiplying them by a 4 × 8 matrix derived from an RS code. Each result of four bytes is then interpreted as a 32-bit word. These words make up the third vector.

for i = 0,....k – 1, and

S = (Sk-1, Sk-2,...,S0)

Note that S lists the words in “reverse” order. For the RS matrix multiply, GF(28) is represented by GF(2)[x]/w(x), where w(x) = x8 + x6 + x3 + x 2 + 1 is another primitive polynomial of degree 8 over GF(2). The mapping between byte values and elements of GF(28) uses the same definition as used for the MDS matrix multiply. Using this mapping, the RS matrix is given by:

The three vectors Me, Mo, and S from the basis of the key schedule.


Previous Table of Contents Next